package leetcode.sword;

import java.util.ArrayList;

public class Solution17 {


    public static void main(String[] args) {

        System.out.println(printNumbers(1));
    }

    /**
     * 生成从1到最大的n位数
     * 如果有大数，考虑使用全排列生成字符串
     * @param n
     * @return
     */
    public static int[] printNumbers(int n) {
        ArrayList<String> generate = generate(n);
        generate.remove(0);
        int[] res = new int[generate.size()];
        for (int i = 0; i < res.length; i++) {
            int idx = 0; //记录最后一个连续0的位置
            String tmp = generate.get(i);
            while (idx<n&&tmp.charAt(idx)=='0') idx++;
            res[i] = idx==n?Integer.parseInt(tmp.substring(n-1)):Integer.parseInt(tmp.substring(idx));
        }
        return res;
    }

    public static ArrayList<String> generate(int n){
        ArrayList<String> res = new ArrayList<>();
        backTrace(res,new StringBuilder(),n);
        return res;
    }

    public static void backTrace(ArrayList<String> all, StringBuilder cur, int n){
        if(cur.length()==n){ //n-1
            all.add(cur.toString());
            return;
        }
        for (int i = 0; i <=9 ; i++) {
            cur.append(String.valueOf(i)); //n
            backTrace(all,cur,n);
            cur.delete(cur.length()-1,cur.length());
        }
    }
}
